public class TreeNode {
    int val;
    TreeNode left,right;
    TreeNode(int x){
        val = x;
    }
    public String toString(){
        return Integer.toString(val);
    }

    public static void traversePreOrder(TreeNode root){
        if(root == null) return;
        System.out.println(root.val);
        traversePreOrder(root.left);
        traversePostOrder(root.right);

    }
    public static void traverseInOrder(TreeNode root){
            if(root == null) return;
            System.out.println(root.val);
            traverseInOrder(root.left);
            System.out.println(root.val);
            traverseInOrder(root.right);

    }

    public static void traversePostOrder(TreeNode root){
            if(root == null) return;
            traversePostOrder(root.left);
            traversePostOrder(root.right);
            System.out.println(root.val);

    }
    public static int[] StrToIntArray(String str){
        str = str.substring(1,str.length()-1);
        String [] strs = str.split(",");
        int [] arr = new int[strs.length];

        for(int i = 0; i < arr.length;i++){
            if(strs[i].equals("null")){
               arr[i] = Integer.MAX_VALUE;
            }else {
                arr[i] = Integer.parseInt(strs[i]);
            }
        }
        return arr;

    }

    public static TreeNode mkTree(String str){
        int [] arr = StrToIntArray(str);
        //System.out.println(arr.length);
        TreeNode []nodes = new TreeNode[arr.length + 1];
        for(int i = 1; i < nodes.length;i++){
            if (arr[i-1] != Integer.MAX_VALUE){
                nodes[i] = new TreeNode(arr[i-1]);
            } else {
                nodes[i] = null;
            }
        }
        TreeNode node = null;
        for(int i = 1; i< nodes.length/2; i++){
            node = nodes[i];
            if(node == null) continue;
            node.left = nodes[2*i];
            node.right = nodes[2*i+1];
        }
        return nodes[1];
    }
    public static void main(String[] args) {
        String str = "[3,9,20,null,null,15,7]";
        TreeNode node = TreeNode.mkTree(str);
        traversePostOrder(node);
        traversePreOrder(node);

    }
}

